{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Table of Contents\n", "* [1. Representing Information](#1.-Representing-Information)\n", "* [2. Representing numbers in different bases](#2.-Representing-numbers-in-different-bases)\n", "\t* [2.1 Positional number systems](#2.1-Positional-number-systems)\n", "\t* [2.2 Converting to base *n*](#2.2-Converting-to-base-*n*)\n", "* [3. Data Types](#3.-Data-Types)\n", "\t* [3.1 Integers](#3.1-Integers)\n", "\t\t* [3.1.1 Unsigned Integers](#3.1.1-Unsigned-Integers)\n", "\t\t* [3.1.2 Signed Integers](#3.1.2-Signed-Integers)\n", "\t\t\t* [3.1.2.1 Signed Magnitude](#3.1.2.1-Signed-Magnitude)\n", "\t\t* [3.1.3 One's Complement](#3.1.3-One's-Complement)\n", "\t\t* [3.1.4 Two's Complement](#3.1.4-Two's-Complement)\n", "\t* [3.2 Floating Point Numbers](#3.2-Floating-Point-Numbers)\n", "\t\t* [3.2.1 To IEEE format](#3.2.1-To-IEEE-format)\n", "\t\t\t* [3.2.1.1 Convert to binary representation](#3.2.1.1-Convert-to-binary-representation)\n", "\t\t\t* [3.2.1.2 Normalize](#3.2.1.2-Normalize)\n", "\t\t\t* [3.2.1.3 Add 127 to exponent, convert to binary](#3.2.1.3-Add-127-to-exponent,-convert-to-binary)\n", "\t\t\t* [3.2.1.4 Combine, leaving off leading 1 of precision](#3.2.1.4-Combine,-leaving-off-leading-1-of-precision)\n", "\t\t* [3.2.2 From IEEE format](#3.2.2-From-IEEE-format)\n", "\t\t\t* [3.2.2.1 From IEEE format](#3.2.2.1-From-IEEE-format)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 1. Representing Information" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "How do we represent data in a computer? [](#cite-colorado)\n", "\n", "At the lowest level, a computer is an electronic machine.\n", "\n", "* works by controlling the flow of electrons\n", "\n", "Easy to recognize two conditions:\n", "\n", "1. presence of a voltage - we'll call this state \"1\"\n", "2. absence of a voltage - we'll call this state \"0\"\n", "\n", "Could base state on value of voltage, but control and detection circuits more complex.\n", "\n", "* compare turning on a light switch to\n", "* measuring or regulating voltage \n", "\n", "[After Gregory Byrd (North Carolina State University), Chris Wilcox, S. Rajopadhye (Colorado State University)](https://www.cs.colostate.edu/~cs270/.Fall13/Notes/Lecture1(C1).pdf)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 2. Representing numbers in different bases" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2.1 Positional number systems" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Consider these positions in a number system:\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "
n3n2n1n0
d3d2d1d0
\n", "\n", "$$\n", "d_3 \\times n^3 + d_2 \\times n^2 + d_1 \\times n^1 + d_0 \\times n^0 \n", "$$\n", "\n", "Consider the number 350 in base 10 (radix 10). That is, n is 10, and thus: \n", "\n", "$$\n", "0 \\times n^3 + 3 \\times n^2 + 5 \\times n^1 + 0 \\times n^0 \n", "$$\n", "\n", "$$\n", "0 \\times 1000 + 3 \\times 100 + 5 \\times 10 + 0 \\times 1 \n", "$$\n", "\n", "Consider the number 0110 in base 2 (radix 2). That is, n is 2, and thus: \n", "\n", "$$\n", "0 \\times n^3 + 1 \\times n^2 + 1 \\times n^1 + 0 \\times n^0 \n", "$$\n", "\n", "$$\n", "0 \\times 8 + 1 \\times 4 + 1 \\times 2 + 0 \\times 1 \n", "$$\n", "\n", "or 6 in base 10." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2.2 Converting to base *n*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To convert a base 10 number to base *n*, use the following algorithm:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "65535 in base 16 is: \n", "FFFF" ] } ], "source": [ "%%python\n", "\n", "def rep(digit):\n", " if digit <= 9:\n", " return str(digit)\n", " elif digit == 10:\n", " return \"A\"\n", " elif digit == 11:\n", " return \"B\"\n", " elif digit == 12:\n", " return \"C\"\n", " elif digit == 13:\n", " return \"D\"\n", " elif digit == 14:\n", " return \"E\"\n", " elif digit == 15:\n", " return \"F\"\n", " else:\n", " return \"?\"\n", "\n", "number = 4096 * 15 + 256 * 15 + 16 * 15 + 15\n", "base = 16\n", "positions = 4\n", "\n", "print(\"%d in base %d is: \" % (number, base))\n", "\n", "for i in range(positions - 1, -1, -1):\n", " digit = (number // base ** i)\n", " number = number - digit * base ** i\n", " print(rep(digit), end=\"\")" ] }, { "cell_type": "code", "execution_count": 53, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0b1110\n" ] } ], "source": [ "%%python\n", "print(bin(14))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 3. Data Types" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3.1 Integers" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "There are two categories of integers (whole numbers):\n", "\n", "* Unsigned integers\n", " * Typically, each bit represents decreasing (from left to right) magnitudes of powers of 2\n", "* Signed integers\n", " * Signed magnitude\n", " * 1's complement\n", " * 2's complement\n", "\n", "Unsigned integers are all positive, and thus you can use all bits to represent positive numbers.\n", "\n", "Signed integers use a bit to represent whether the integer is positive or negative." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3.1.1 Unsigned Integers" ] }, { "cell_type": "markdown", "metadata": { "format": "row" }, "source": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "
NumberBits
00000
10001
20010
30011
40100
50101
60110
70111
81000
91001
101010
111011
121100
131101
141110
151111
\n", "\n", "**What is the largest unsigned integer using 16 bits? Using 32 bits?**" ] }, { "cell_type": "code", "execution_count": 58, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "15\n" ] } ], "source": [ "%%python\n", "\n", "print(2 ** 4 - 1)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "%%processing\n", "\n", "println(pow(2, 4) - 1);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3.1.2 Signed Integers" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Unsigned integers are nice and simple. But, for much of what we want our LC-3 to do might involve negative numbers.\n", "\n", "How can we represent negative numbers?\n", "\n", "It could be completely arbitrary... but we want to keep the circuits as simple as we can make them. So, it makes sense to have patterns that we can take advantage of." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### 3.1.2.1 Signed Magnitude" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The simplest pattern (at least for humans) might be the \"signed magnitude\"... just use the left-most bit to mean negative." ] }, { "cell_type": "markdown", "metadata": { "format": "tab" }, "source": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "
NumberBits
-71111
-61110
-51101
-41100
-31011
-21010
-11001
-01000
00000
10001
20010
30011
40100
50101
60110
70111
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3.1.3 One's Complement" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "
NumberBits
-71000
-61001
-51010
-41011
-31100
-21101
-11110
-01111
00000
10001
20010
30011
40100
50101
60110
70111
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "However, we have to implement mathematics in a circuit (as we will see). We want that the Arithmetic and Logic Unit circuit to be able to add any two binary numbers and get the appropriate binary number.\n", "\n", "What we want is that **REPRESENTATION(a + b) == REPRESENTATION(a) + REPRESENTATION(b)**\n", "\n", "Problems with 1's complement and Signed magnitude:\n", "\n", "* negative zero?\n", "* 0001 + 1110 = 1111\n", "* does 1111 == 0000? (one's complement); 1000 == 0000? (signed magnitude)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3.1.4 Two's Complement" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "
NumberBits
-81000
-71001
-61010
-51011
-41100
-31101
-21110
-11111
00000
10001
20010
30011
40100
50101
60110
70111
\n", "\n", "Consider:\n", "\n", "* no negative zero\n", "* 0111 + 1000 = 1111... correct?\n", "\n", "Now, we have solved all of the negative zero issues.\n", "\n", "**What is the range of numbers represented in 16 bits using 2's complement?**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3.2 Floating Point Numbers" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Could be used just to indicate where a decimal place\n", "\n", "Used to represent really big numbers and really small numbers.\n", "\n", "Consider that we have 32 bits to use. The *IEEE Standard for Floating Point Arithmetic* defined the following representation:\n", "\n", "* 1 bit for the sign (0 = positive, 1 = negative)\n", "* 8 bits for exponent (offset by 127)\n", "* 23 bits for precision (leading 1 assumed)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3.2.1 To IEEE format" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Consider converting:\n", "\n", "$$ \n", "-6 \\dfrac{5}{8}\n", "$$\n", "\n", "to IEEE floating-point representation." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### 3.2.1.1 Convert to binary representation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "
n3n2n1n0Decimaln-1n-2n-3n-4
d3d2d1d0.d-1d-2d-3d-4
\n", "\n", "\n", "Just as before we see how many column values will go into a number, we continue for $n^{-1}$...\n", "\n", "$$\n", "0 \\times n^3 + 1 \\times n^2 + 1 \\times n^1 + 0 \\times n^0 + 1 \\times n^{-1} + 0 \\times n^{-2} + 1 \\times n^{-3}\n", "$$\n", "\n", "$$\n", "0 \\times 8 + 1 \\times 4 + 1 \\times 2 + 0 \\times 1 + 1 \\times \\dfrac{1}{2} + 0 \\times \\dfrac{1}{4} + 1 \\times \\dfrac{1}{8}\n", "$$\n", "\n", "or:\n", "\n", "-0110.101" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### 3.2.1.2 Normalize" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Move the decimal place to left or right to get a single 1 to the left of the decimal place. Count how many places and in which direction:\n", "\n", "-0110.101\n", "\n", "becomes:\n", "\n", "-01.10101\n", "\n", "with 2 moves (exponent)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### 3.2.1.3 Add 127 to exponent, convert to binary" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "2 + 127 = 129\n", "\n", "which is:\n", "\n", "100000001\n", "\n", "in binary." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### 3.2.1.4 Combine, leaving off leading 1 of precision" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "1 100000001 10101\n", "\n", "and pad to a total of 32 bits:\n", "\n", "1 100000001 10101000000000000000000" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3.2.2 From IEEE format" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Consider:\n", "\n", "00111101100000000000000000000000\n", "\n", "Do the reverse:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### 3.2.2.1 First digit is sign\n", "\n", "Break into parts:\n", "\n", "0 01111011 00000000000000000000000\n", "\n", "It is positive!\n", "\n", "#### 3.2.2.1 Next 8 bits is exponent, minus 127\n", "\n", "Convert next 8 unsigned bits into decimal, and subtract 127:\n", "\n", "01111011 is 123\n", "\n", "123 - 127 = -4\n", "\n", "#### 3.2.2.1 Get precision\n", "\n", "Put a one in front of the last 23 bits:\n", "\n", "1.00000000000000000000000\n", "\n", "and move the decimal spot by the exponent. In this case, 4 places to the left:\n", "\n", "0.000100000000000000000000000\n", "\n", "Convert to decimal:\n", "\n", "$$\n", "0 * \\dfrac{1}{2} + 0 * \\dfrac{1}{4} + 0 * \\dfrac{1}{8} + 1 * \\dfrac{1}{16} ...\n", "$$\n", "\n", "#### 3.2.2.1 All together\n", "\n", "$$\n", "+ \\dfrac{1}{16}\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": false }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "Traceback (most recent call last):\n", " File \"/usr/lib/python3.4/site-packages/metakernel-0.10.5-py3.4.egg/metakernel/magics/python_magic.py\", line 63, in eval\n", " exec(code.strip(), self.env)\n", " File \"\", line 1, in \n", "TypeError: 'float' object cannot be interpreted as an integer\n", "\n" ] } ], "source": [ "%%python\n", "\n", "for i in range(0, 10, .1):\n", " print(i)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Calysto LC3", "language": "gas", "name": "calysto_lc3" }, "language_info": { "file_extension": ".asm", "mimetype": "text/x-gas", "name": "gas" } }, "nbformat": 4, "nbformat_minor": 0 }